/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
export var strStr = function (haystack, needle) {
  return haystack.indexOf(needle)
}

/**
 * kmp算法（官方题解）
  https://leetcode.cn/problems/implement-strstr/solution/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86/
  https://leetcode.cn/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode-solution-ds6y/
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
export var strStr2 = function (haystack, needle) {
  const n = haystack.length,
    m = needle.length
  if (m === 0) {
    return 0
  }
  const pi = new Array(m).fill(0)
  for (let i = 1, j = 0; i < m; i++) {
    while (j > 0 && needle[i] !== needle[j]) {
      j = pi[j - 1]
    }
    if (needle[i] == needle[j]) {
      j++
    }
    pi[i] = j
  }
  for (let i = 0, j = 0; i < n; i++) {
    while (j > 0 && haystack[i] != needle[j]) {
      j = pi[j - 1]
    }
    if (haystack[i] == needle[j]) {
      j++
    }
    if (j === m) {
      return i - m + 1
    }
  }
  return -1
}
